package demo.practice.dp;

import java.util.HashSet;
import java.util.Set;

public class P416_2 {


    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if ((sum & 1) == 1) {//基数
            return false;
        }
        int target = sum / 2;
        //boolean dp[][] = new boolean[nums.length][target + 1];
        Set<Integer> visited = new HashSet<>();
        visited.add(0);
        for (int i = 0; i < nums.length; i++) {
            Set<Integer> c = new HashSet<>();
            for (Integer v : visited) {
                int ct = v + nums[i];
                if(ct>target) {
                    // 已经越界的，不用再放进去，可以提高性能
                    continue;
                }
                // 选择当前位置的nums[i]
                c.add(ct);
                // 不选择当前位置的nums[i]，因为v本身已经在visited里了，可以不写
                //c.add(v+0);
                if (ct == target) {
                    return true;
                }
            }
            visited.addAll(c);
        }
        return false;
    }

}
